#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    return dfs(root, p, q);
}

TreeNode* dfs(TreeNode* root, TreeNode* p, TreeNode* q)
{
    if (root == nullptr)     return nullptr;
    int t1 = root->val - p->val;
    int t2 = root->val - q->val;
    if (t1 > 0 && t2 > 0)    return dfs(root->left, p, q);
    if (t1 < 0 && t2 < 0)  return dfs(root->right, p, q);
    return root;
}